package com.xjl.sort;

import com.xjl.utils.SortUtil;

import java.util.Arrays;

/**
 * @描述： 给定一个数组，求如果排序后，相邻两数之间的最大差值，
 * @要求： 时间复杂度为O（Ｎ），且不能用基于比较的排序
 * @作者： 许JIAN林
 */
public class TongSort {
    public static int tongSort(int[] arr) {
        //1.求出数组的最大值和最小值
        //2.确定所需要的筒数
        //3.定义桶元素，由于本题只关注差值，所以我们只关心每一个桶的最大值，和最小值，和是否为空桶
        //4.将对应的元素放入相对应的桶中（需要计算出该元素应存放到哪一个桶中）
        //5.求最大差值
        int lenth = arr.length;
        int max = Integer.MIN_VALUE; //系统最小值
        int min = Integer.MAX_VALUE;//系统最大值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        boolean[] hasNum = new boolean[lenth + 1]; //判断每个桶是否为空
        int[] maxs = new int[lenth + 1];
        int[] mins = new int[lenth + 1];

        //确定每一桶的最大值和最小值
        for (int i = 0; i < arr.length; i++) {
            int flag = backet(arr[i], max, min, lenth); // 实际值有 len 个桶，由于是从0开始的
            maxs[flag] = hasNum[flag] ? Math.max(maxs[flag], arr[i]) : arr[i] ;
            mins[flag] = hasNum[flag] ? Math.min(mins[flag], arr[i]) : arr[i] ;
            hasNum[flag] = true;
        }

        int res =0;

        int lastMax = maxs[0];
        int i = 1;
        for (; i < lenth; i++ ){
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;

    }

    /**
     * 判断该素质应该位于哪一个桶
     * @param num
     * @param max
     * @param min
     * @param lenth
     * @return
     */
    private static int backet(int num, int max, int min, int lenth) {
        // 实际值有 len 个桶，由于是从0开始的
        return  (int)((num - min) * lenth / (max - min)) ;
    }


    public static void main(String[] args) {
        int[] arr = SortUtil.getarr(5, 10);
//        int[] arr = {3,6,6,9,9};
        int i = tongSort(arr);
        System.out.println("最大差值为："+ i );
        Arrays.sort(arr);
        SortUtil.display(arr);


    }
}